Convexity is a very strong property, but a weaker version often suffices. Consider this version: a polygon is ``locally convex'' if there exists some point $p$ in the interior of the polygon such that, for each vertex $v$ of the polygon, the line segment $\overline{pv}$ lies entirely within the polygon. (This is much as in the geometric definition of a convex polygon, except that only one endpoint of the segment is arbitrary.)
\\\\
Design and analyze a randomized algorithm that, given just the polygon (by a
counterclockwise list of its vertices along the perimeter), decides in linear expected time whether the polygon is locally convex.
\\\\
Let's consider  ``locally convex'' polygon and where the point $p$ should be. We know that for each vertex $v$ of the polygon, the line segment $\overline{pv}$ lies entirely within the polygon. So we can see any vertex of polygon from the point $p$. Thus, we also can see any edge of polygon. If we can see an edge from a point of interior of polygon, it means that this point is in the halfplane determined as the left halfplane with a line subtending given edge (left with respect to the direction of the edge --- that is the halfplane with interior of polygon). As it should hold for all edges of polygon, then the point $p$ have to lie in the intersections of halfplanes constructed for all edges. We can see also that any point from this intersection can be chosen as $p$, that is as the point for which condition of ``local convexity'' holds.

So what we want to check is whether this intersection of all halfplanes is empty or not. To do so in linear time, we can treat this problem as the problem of linear programming with 2 variables $x$ and $y$, as the constraints are represented by linear inequations (halfplanes). The objective function should be linear, so let's use $Ax+By$, for any random $A,B$. Solution of this linear programming problem can be found in $O(n)$ randomized time: (Kenneth L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small, 1995). Thus, if the solution exists, then it will return the point from intersection of all halfplanes (as the point satisfying the constraints), if it doesn't exist, then there is no such point and the polygon is not  locally convex.